Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Аналіз алгоритму сортування методом

Інформація про навчальний заклад

ВУЗ:
Вінницькій національний технічний університет
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
ФІТКІ
Кафедра:
КН

Інформація про роботу

Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН 2
Варіант:
13

Частина тексту файла

Міністерство освіти і науки України Вінницький національний технічний університет Факультет інформаційних технологій і комп’ютерної інженерії Кафедра комп’ютерних наук Лабораторна робота №3 З дисципліни: Теорія алгоритмів Тема: «Аналіз алгоритму сортування методом злиття» Вінниця, 2017 Аналіз алгоритму сортування методом злиття Мета: навчитись аналізувати алгоритми на прикладі алгоритму сортування методом злиття Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй». В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової. Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності Приклад реалізації на Java public class Solution { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Введіть кількість елементів масива"); int num = Integer.parseInt(reader.readLine()); int arr[] = new int[num]; System.out.println("Рaндомний массив:"); for(int i = 0; i < arr.length; i++) { //элементу массива присваивается случайное число от 0 до 99 arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + " "); } long timeout= System.currentTimeMillis(); mergesort(arr); timeout = System.currentTimeMillis() - timeout; System.out.println("Час затрачений на виконання сортування = "+ timeout+ "мc"); } public static void mergesort(int[] arr) { System.out.println("\nВідсортований масив:"); int n = arr.length; boolean c = true; int i = 0; int i1 = 0; int i2 = 0; int n1 = 0; int n2 = 0; int[] barr = new int[n]; int mergelen = 0; barr = new int[n]; mergelen = 1; while (mergelen < n) { if (c) { i = 0; while (i + mergelen <= n) { i1 = i + 1; i2 = i + mergelen + 1; n1 = i + mergelen; n2 = i + 2 * mergelen; if (n2 > n) { n2 = n; } while (i1 <= n1 | i2 <= n2) { if (i1 > n1) { while (i2 <= n2) { i = i + 1; barr[i - 1] = arr[i2 - 1]; i2 = i2 + 1; } } else { if (i2 > n2) { while (i1 <= n1) { i = i + 1; barr[i - 1] = arr[i1 - 1]; i1 = i1 + 1; } } else { if (arr[i1 - 1] > arr[i2...
Антиботан аватар за замовчуванням

24.10.2018 17:10

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини